package test;

public class GetMaximumGold {
	int m,n;
    int ret;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] visit;
    //dfs: 以[i,j]位置出发，返回能获得的最大收益
    public void dfs(int[][] grid,int i,int j,int sum){
    	//第二个更新时机： ret=Math.max(ret,sum),在入口直接更新
    	
        sum+=grid[i][j];
        //枚举上下左右四个方向
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&y>=0&&x<m&&y<n&&grid[x][y]!=0&&visit[x][y]==false){
                visit[x][y]=true;
                dfs(grid,x,y,sum);
                visit[x][y]=false;
            }
        }
        //当走到这里，即循环结束，说明： 没有可以继续走的方向了 =》 收集结果
        ret=Math.max(sum,ret);
    }
    public int getMaximumGold(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        ret=Integer.MIN_VALUE;
        visit=new boolean[m][n];
        //枚举每一个可能的入口
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //只要黄金不为0，就可以作为入口
                if(grid[i][j]!=0){
                    visit[i][j]=true;
                    dfs(grid,i,j,0);
                    visit[i][j]=false;
                }
            }
        }
        //可能金矿没有金子，因此最好直接将ret初值设置为0
        return ret==Integer.MIN_VALUE?0:ret;
    }
}
